package dp;

import java.util.HashSet;
import java.util.Set;

public class P55 {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        Set<Integer> posSet = new HashSet<Integer>();
        posSet.add(0);
        while (posSet.size() != 0) {
            Set<Integer> newSet = new HashSet<>();
            for (int pos : posSet) {
                if (pos == n - 1) {
                    return true;
                } else {
                    for (int i = 1; i <= nums[pos]; i++) {
                        if (pos + i == n - 1) {
                            return true;
                        } else if (pos + i < n) {
                            newSet.add(pos + i);
                        }
                    }
                }
            }
            posSet = newSet;
        }
        return false;
    }

    boolean dpMethod(int[] nums) {
        int len = nums.length;
        int[][] dp = new int[len][len];
        for (int i = 0; i < len; i++) {
            //1. 检查能否到dp[]
            boolean flag = false;
            int idx = i - 1;
            while (idx >= 0) {
                if (dp[idx][i] == 1) {
                    flag = true;
                    break;
                }
                idx--;
            }
            if (i != 0 && !flag) { // 不能到达此结点
                continue;
            }
            //2. 装填dp[i][.]
            for (int j = 1; j <= nums[i]; j++) {
                dp[i][i + j] = 1;
                if (i + j == len - 1) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{2, 3, 1, 1, 4};
        boolean b = new P55().dpMethod(nums);
        System.out.println(b);
    }
}
